Give the tight Big-Oh bound for the running time (as a function of n)
of each of the following code fragments.


(assume n is the length of s, length() and charAt() are O(1))

static int StrtoNum(String s) {
    int r = 0;
    for (int i = 0; i < s.length(); i++) {
	r = r * 10 + s.charAt(i) - '0';
    }
    return r;
}


(assume println() is O(1))

void Han(int n, char x, char y, char z) {
    if (n > 0) {
      Han(n-1, x, z, y);
	System.out.println(n + " " + x + " " + y);
	Han(n-1, z, y, x);
    }
}


(assume n = length of s, length() and charAt() are O(1), substring() is O(n))

boolean Check(String s) {
    if (s.length() <= 1) {
        return true;
    } else if (s.charAt(0) == s.charAt(s.length()-1)) {
	String sub = s.substring(1, s.length()-1);
	return Check(sub);
    } else {
        return false;
    }
}


(assume print() and println() are O(1))

static void Print(int[][] m, int n) {
    int i, j;
    for (i = 0; i < n; i++) {
	for (j = 0; j < n; j++) {
	    System.out.print(m[i][j] + " ");
	}
	System.out.println();
    }
}








Algorithm A is O(logn) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm A take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm A?


Algorithm B is O(2^n) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm B take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm B?


Algorithm C is O(n) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm C take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm C?


Algorithm D is O(1) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm D take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm D?


Algorithm E is O(n^2) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm E take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm E?


Algorithm F is O(n^3) and it completes a problem of size 1024 in 2 seconds.
How long will algorithm F take to complete a problem of size 4096?
How large a problem can be solved in 4 seconds using algorithm F?








The following table gives measured times for program A on a number of
problem sizes. What big-oh function best describes the time for
program A?


size time
 100  10
 200  10
 400  10
 800  10
1600  10


 128 7
 256 8
 512 9
1024 10
2048 11


1   10
2   100
3   1000
4   10000
5   100000


10   1110
20   8420
30   27930
40   65640
50   127550











Suppose the following array is given as input to binary search (with
three-way compares) and the search is looking for the value 77.
List the part of the array in which the algorithm is still searching
after each major step of the binary search algorithm,

11 15 16 22 33 44 48  55  58 62 66 72 77 88 99










Consider the following Java-like program.

Stack S = new Stack();
List L = new List();
S.push(4);
S.push(2);
S.push(1);
S.push(8);
while (!S.isEmpty())
    L.add(S.pop());

What are the contents of the list L at the end of the program?



Consider the following Java-like program.

Queue Q = new Queue();
List L = new List();
Q.enqueue(4);
Q.enqueue(2);
Q.enqueue(1);
Q.enqueue(8);
while (!Q.isEmpty())
    L.add(Q.dequeue());

What are the contents of the list L at the end of the program?



Consider the following Java-like program.

PriorityQueue Q = new PriorityQueue();
List L = new List();
Q.insert(4);
Q.insert(2);
Q.insert(1);
Q.insert(8);
while (!Q.isEmpty())
    L.add(Q.deleteMin());

What are the contents of the list L at the end of the program?











Suppose you have been asked to implement software solutions for each
of the applications listed below. For each application, indicate which
data type would be most effective in solving the problem.


An inventory application that records the quantity of each item stored
in the inventory.

A hard drive that receives a number of block read requests and
optimizes head movement by selecting the next request to process based
on which block address is closest to the current head position.

A classroom scheduling application that allows the user to find the
course number, name, section number, and instructor for a given
classroom and time of day.

An application that stores a number of tasks that need to be done and
allows the user to insert, delete, and edit tasks while keeping the
tasks stored in the order given by the user.

An address book that stores name, address, and phone for a number of
people.

An ATM machine that records date, time, account number, and amount for
each transaction it processes.











Suppose the following array is given as input to insertion sort.
Give the content of the array after each major step of insertion
sort.

8 7 2 9 4 8 5 4 3


Suppose the following array is given as input to selection sort.
Give the content of the array after each major step of selection
sort.

8 7 2 9 4 8 5 4 3


Suppose the following array is given as input to mergesort.
What is the content of the array in the middle of 
the top-level execution of mergesort after the two recursive calls 
to mergesort have completed but before the final call to merge?

8 7 2 9 4 8 5 4 3


Suppose the following array is given as input to quicksort
(with median-of-three partitioning and a cutoff of 3).
What is the content of the array after the array has been 
partitioned for the first time but before making the two recursive
calls to quicksort?

8 7 2 9 4 8 5 4 3